package william.greedy;

/**
 * @author ZhangShenao
 * @date 2024/3/31
 * @description <a href="https://leetcode.cn/problems/is-subsequence/description/">...</a>
 */
public class Leetcode392_判断子序列 {
    /**
     * 从头开始,对两个字符串进行逐个字符比对
     * 针对s串中的每个字符,尝试在t中进行查找,如果未找到则返回false
     * <p>
     * 时间复杂度O(N) 两个字符串各遍历一遍
     * 空间复杂度O(1)
     */
    public boolean isSubsequence(String s, String t) {
        //边界条件校验
        if (s == null || s.isEmpty()) {
            return true;
        }
        if (t == null || t.isEmpty()) {
            return false;
        }

        //从头开始,对两个字符串进行逐个字符比对
        int sIdx = 0;
        int tIdx = 0;
        while (sIdx < s.length() && tIdx < t.length()) {
            char sc = s.charAt(sIdx);
            char tc = t.charAt(tIdx);
            if (sc == tc) {  //当前字符匹配,继续判断下一字符
                sIdx++;
                tIdx++;
            } else { //当前字符不匹配,继续在t串中寻找
                tIdx++;
            }
        }

        //判断s中的字符是否都在t中出现了
        return (sIdx == s.length());
    }
}
